home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 1.iso / ARGONET / PD / PROGRAMMING / DESKLIBC / SOURCES.ZIP / DeskLib / !DLSources / Libraries / Mem / c / MidExtend < prev    next >
Text File  |  1995-06-18  |  12KB  |  422 lines
  1. /*
  2.     ####             #    #     # #
  3.     #   #            #    #       #          The FreeWare C library for 
  4.     #   #  ##   ###  #  # #     # ###             RISC OS machines
  5.     #   # #  # #     # #  #     # #  #   ___________________________________
  6.     #   # ####  ###  ##   #     # #  #                                      
  7.     #   # #        # # #  #     # #  #    Please refer to the accompanying
  8.     ####   ### ####  #  # ##### # ###    documentation for conditions of use
  9.     ________________________________________________________________________
  10.  
  11.     File:    Mem.MidExtend.c
  12.     Author:  Copyright © 1993, 1995 Jason Williams and Jason Howat
  13.     Version: 2.00 (18 Jun 1995)
  14.     Purpose: Dynamic memory manager - reallocation
  15. */
  16.  
  17. #include "Desklib:Error.h"
  18. #include "MemDefs.h"
  19.  
  20. #include <string.h> 
  21.  
  22. #ifdef MEM__DEBUG
  23. #include <stdio.h>
  24. #endif
  25.  
  26.  
  27. static BOOL Mem__MidExtendNoCompact(mem_anchor *anchor, mem_header *chunk, int at, int by)
  28. {
  29.   int         available = chunk->realsize,
  30.               olddatasize,
  31.               newdatasize;
  32.   mem_header *nextchunk = (mem_header *)((int)chunk + chunk->realsize),
  33.              *prevchunk = (mem_header *)((int)chunk - chunk->prevrealsize),
  34.              *newchunk = chunk;
  35.   BOOL        now_last = (chunk == mem__lastchunk);
  36.   char       *source,
  37.              *destination;
  38.  
  39.   /* check space in adjoining blocks and use if available */
  40.   if((chunk != mem__lastchunk) && (ISFREE(nextchunk)))
  41.   {
  42.     available += nextchunk->realsize;
  43.     now_last = (nextchunk == mem__lastchunk);
  44.   }
  45.  
  46.   if(((int)chunk != mem__heap) && (ISFREE(prevchunk)))
  47.   {
  48.     available += prevchunk->realsize;
  49.     newchunk = prevchunk;
  50.   }
  51.  
  52.   newdatasize = chunk->datasize + by;
  53.   source = (char *)chunk + sizeof(mem_header);
  54.   olddatasize = chunk->datasize;
  55.  
  56.   if(available >= CHUNKSIZE(chunk->datasize + by))
  57.   {
  58.     destination = (char *)((int)newchunk + sizeof(mem_header));
  59.     *chunk->handle = destination;
  60.     newchunk->handle = chunk->handle;
  61.     newchunk->realsize = available;
  62.     newchunk->datasize = newdatasize;
  63.     mem__free -= WORDALIGN(newdatasize) - WORDALIGN(olddatasize);
  64.  
  65.     if(!now_last)
  66.     {
  67.       mem_header *nn = (mem_header *)((int)newchunk + available);
  68.       nn->prevrealsize = available;
  69.     }
  70.  
  71.     memmove(destination, source, at);
  72.     memmove(destination + at + by, source + at, olddatasize - at);
  73.  
  74.     Mem__SplitOffFreeChunk(newchunk);
  75.   }
  76.   else /* try to alloc block of new size and copy old one over */
  77.   {
  78.     if(!Mem_Alloc((mem_anchor *)&destination, newdatasize))
  79.       return FALSE;
  80.  
  81.     memmove(destination, source, at);
  82.     memmove(destination + at + by, source + at, olddatasize - at);
  83.  
  84.     Mem_Free(anchor);
  85.     *anchor = destination;
  86.     Mem__FindChunk((mem_anchor *)&destination, &chunk);
  87.     chunk->handle = anchor;
  88.   }
  89.  
  90.   return TRUE;
  91. }
  92.  
  93. extern BOOL Mem_MidExtend(mem_anchor *anchor, int at, int by)
  94. /*  Enlarges or reduces a Mem chunk by moving all data beyond 'at' by
  95.  *  'by' bytes up or down in memory. 'at' is an offset within the chunk.
  96.  *
  97.  *  Goes to rather a lot of effort to avoid moving the base address of
  98.  *  this chunk and others, but if mem_autocompact allows, it will compact
  99.  *  if it is absolutely necessary in order to manage the extension.
  100.  *
  101.  *  Returns TRUE if it succeeds
  102.  */
  103. {
  104.   mem_header *chunk,
  105.              *bestfit = NULL,
  106.              *start, *end,
  107.              *best_start = NULL, *best_end,
  108.              *scan_start, *scan_end,
  109.              *end_of_heap;
  110.   int         bestfit_size,
  111.               best_move, best_free,
  112.               move_count, free_count,
  113.               needed,
  114.               newdatasize, extchunksize;
  115.   char       *source,
  116.              *destination;
  117.  
  118.  
  119.   if(by == 0)         /* Zero bytes? Certainly sir! Anything else? */
  120.     return(TRUE);
  121.  
  122.   if(at < 0 || !Mem__FindChunk(anchor, &chunk))
  123.     return(FALSE);
  124.  
  125.   if(at > chunk->datasize)
  126.     return(FALSE);
  127.  
  128.   source = (char *)chunk + sizeof(mem_header);
  129.  
  130.   /* ------ Reduce chunk ------ */
  131.   if (by < 0)                            /* Reducing the size of the chunk   */
  132.   {
  133.     if (-by > at) by = -at;              /* Can't delete past start of chunk */
  134.  
  135.     mem__free += WORDALIGN(chunk->datasize) - WORDALIGN(chunk->datasize + by);
  136.  
  137.     memmove(source + at + by, source + at, chunk->datasize - at);
  138.     chunk->datasize += by;               /* Shrink data area of this block   */
  139.  
  140.     Mem__SplitOffFreeChunk(chunk);       /* Return any free space for use    */
  141.     /* The anchor has not changed */
  142.     return(TRUE);
  143.   }
  144.  
  145.  
  146.   /* ------ Extend chunk ------ */
  147.   if(mem_autocompact == mem_NOCOMPACT)
  148.     return Mem__MidExtendNoCompact(anchor, chunk, at, by);
  149.   else /*  allowed to relocate other blocks in the search for the cheapest way
  150.         *  of creating enough space for the extension
  151.         */
  152.   {
  153.     newdatasize = chunk->datasize + by;
  154.     extchunksize = CHUNKSIZE(newdatasize);
  155.     /* needed: is the number of free bytes required to perform the extension
  156.                (will be a multiple of 4) */
  157.     needed = WORDALIGN(newdatasize) - WORDALIGN(chunk->datasize);
  158.  
  159.     /* ensure there is enough space _before_ we go searching for the cheapest
  160.      * way of using it
  161.      */
  162.     if(mem__free < needed)
  163.     {
  164.       /* extend the heap by at least (needed - mem__free) bytes */
  165.       int extra = needed - mem__free,
  166.           prevsize = mem__heapsize;
  167.  
  168.       mem__heapsize = Mem__HeapSize(mem__heapsize + extra + 16);
  169.       mem__free += mem__heapsize - prevsize;
  170. #ifdef MEM__DEBUG
  171. fprintf(stderr, "grow heap: %8x\n", mem__heapsize - prevsize);
  172. fflush(stderr);
  173. #endif
  174.       mem__lastchunk->realsize = mem__heap + mem__heapsize - (int)mem__lastchunk;
  175.  
  176.       if(mem__free < needed)
  177.       {
  178.         Mem__SplitOffFreeChunk(mem__lastchunk);
  179.         Mem__ReduceSlot();
  180.         return FALSE;     /* unable to get enough freespace to do extension */
  181.       }
  182.     }
  183.  
  184.     start = chunk;
  185.     end = (mem_header *)((int)chunk + chunk->realsize);
  186.     end_of_heap = (mem_header *)(mem__heap + mem__heapsize);
  187.  
  188.     if(start->realsize >= extchunksize)
  189.     {
  190.       bestfit = start;
  191.       bestfit_size = start->realsize;
  192.     }
  193.  
  194.     move_count = start->datasize;
  195.     free_count = start->realsize - CHUNKSIZE(start->datasize);
  196.   
  197.     /* Scan backwards from chunk to find start of possible run of blocks */
  198.     while((free_count < needed) && ((int)start != mem__heap))
  199.     {
  200.       int used;
  201.   
  202.       start = (mem_header *)((int)start - start->prevrealsize);
  203.   
  204.       if(ISFREE(start))
  205.       {
  206.         used = 0;
  207.  
  208.         if(((bestfit == NULL) || (bestfit_size > start->realsize)) &&
  209.            (start->realsize >= extchunksize))
  210.         {
  211.           bestfit = start;
  212.           bestfit_size = bestfit_size;
  213.         }
  214.       }
  215.       else
  216.       {
  217.         used = CHUNKSIZE(start->datasize);
  218.         move_count += used;
  219.       }
  220.  
  221.       free_count += start->realsize - used;
  222.     }
  223.  
  224.     scan_start = start;
  225.  
  226.     /* Alternately advance end/start forwards keeping track of count of bytes
  227.        to be moved, remembering start/end points for run of blocks with
  228.        minimum.  At the same time scan for a single free block which is big
  229.        enough to hold the entire extended block. Check for when start == chunk
  230.        and adjust *_count variables accordingly */
  231.     while(1)
  232.     {
  233.       /* advance end and adjust *_count stats until free_count >= needed */
  234.       while((free_count < needed) && (end < end_of_heap))
  235.       {
  236.         int used;
  237.  
  238.         if(ISFREE(end))
  239.         {
  240.           used = 0;
  241.  
  242.           if(((bestfit == NULL) || (bestfit_size > end->realsize)) &&
  243.              (end->realsize >= extchunksize))
  244.           {
  245.             bestfit = end;
  246.             bestfit_size = bestfit_size;
  247.           }
  248.         }
  249.         else
  250.         {
  251.           used = CHUNKSIZE(end->datasize);
  252.           move_count += used;
  253.         }
  254.  
  255.         free_count += end->realsize - used;
  256.  
  257.         end = (mem_header *)((int)end + end->realsize);
  258.       }
  259.  
  260.       /* check stats and copy to best_* if needed */
  261.       if((free_count >= needed) &&
  262.          ((best_start == NULL) || (best_move > move_count)))
  263.       {
  264.         best_start = start;
  265.         best_end = end;
  266.         best_move = move_count;
  267.         best_free = free_count;
  268.       }
  269.   
  270.       if(start == chunk)
  271.         break;
  272.  
  273.       {
  274.         int used;
  275.  
  276.         /* adjust *_count stats and advance start one block */
  277.         if(!ISFREE(start))
  278.         {
  279.           used = CHUNKSIZE(start->datasize);
  280.           move_count -= used;
  281.         }
  282.         else
  283.           used = 0;
  284.         free_count -= start->realsize - used;
  285.       }
  286.  
  287.       start = (mem_header *)((int)start + start->realsize);
  288.  
  289.       if(start == chunk)
  290.         move_count -= sizeof(mem_header) + at;
  291.     }
  292.  
  293.     scan_end = end;
  294.  
  295.     /* Consider cost of moving whole block to larger free block and choose
  296.      * cheapest option for the extension of the block.
  297.      * NB: as we have already ensured that (mem__free >= needed), best_start
  298.      *     must be non-NULL, as a run of blocks has to exist.
  299.      */
  300.     if(best_move > chunk->datasize)
  301.     {
  302.       /* check chunks before scan_start and after scan_end for single free
  303.        * block that is large enough for the extended block, as it is cheaper
  304.        * to relocate target block.
  305.        */
  306.       mem_header *check;
  307.  
  308.       check = (mem_header *)mem__heap;
  309.       while(check < scan_start)
  310.       {
  311.         if(ISFREE(check))
  312.         {
  313.           if(((bestfit == NULL) || (bestfit_size > check->realsize)) &&
  314.              (check->realsize >= extchunksize))
  315.           {
  316.             bestfit = check;
  317.             bestfit_size = check->realsize;
  318.           }
  319.         }
  320.  
  321.         check = (mem_header *)((int)check + check->realsize);
  322.       }
  323.  
  324.       check = scan_end;
  325.       while(check < end_of_heap)
  326.       {
  327.         if(ISFREE(check))
  328.         {
  329.           if(((bestfit == NULL) || (bestfit_size > check->realsize)) &&
  330.              (check->realsize >= extchunksize))
  331.           {
  332.             bestfit = check;
  333.             bestfit_size = check->realsize;
  334.           }
  335.         }
  336.  
  337.         check = (mem_header *)((int)check + check->realsize);
  338.       }
  339.     }
  340.  
  341.     if((bestfit != NULL) && (best_move > chunk->datasize))
  342.     {
  343.       /* it is cheaper to relocate entire chunk */
  344. #ifdef MEM__DEBUG
  345. fprintf(stderr, "relocate: bestfit %p\n", bestfit);
  346. fflush(stderr);
  347. #endif
  348.  
  349.       /* copy data */
  350.       destination = (char *)bestfit + sizeof(mem_header);
  351.       memmove(destination, source, at);
  352.       memmove(destination + at + by, source + at, chunk->datasize - at);
  353.       
  354.       /* update heap control structures */
  355.       bestfit->handle = chunk->handle;
  356.       bestfit->datasize = newdatasize;
  357.       Mem_Free(anchor);
  358.       *bestfit->handle = destination;
  359.       mem__free -= extchunksize;
  360.  
  361.       Mem__SplitOffFreeChunk(bestfit);
  362.  
  363.       return(TRUE);
  364.     }
  365.     else
  366.     {
  367.       /* perform extension by:
  368.        *   compacting region defined by best_start/best_end
  369.        *   move data to new locations
  370.        *   update headers of surrounding and target chunks
  371.        */
  372.       mem_header *newchunk;
  373.       int         newchunksize,
  374.                   oldchunksize;
  375.  
  376.       if(best_start < chunk)  /* must be free space available before chunk */
  377.       {
  378.         Mem__ShuffleDown(best_start, chunk);
  379.         newchunk = (mem_header *)((int)chunk - chunk->prevrealsize);
  380.       }
  381.       else
  382.         newchunk = chunk;
  383.       destination = (char *)((int)newchunk + sizeof(mem_header));
  384.  
  385.       if(best_end > (mem_header *)((int)chunk + chunk->realsize))
  386.         Mem__ShuffleUp(chunk, best_end);
  387.  
  388.       newchunksize = chunk->realsize;
  389.       if(best_start < chunk)
  390.         newchunksize += newchunk->realsize;
  391.  
  392.       if(extchunksize > newchunksize)  /* sanity check */
  393.         Error_ReportFatalInternal(0, "Unexpected failure in Mem_MidExtend");
  394.  
  395.       /* update anchors/links */
  396.       oldchunksize = chunk->datasize;
  397.       newchunk->handle = chunk->handle;
  398.       newchunk->datasize = newdatasize;
  399.       newchunk->realsize = newchunksize;
  400.       *(newchunk->handle) = destination;
  401.  
  402.       /* move data */
  403.       memmove(destination, source, at);
  404.       memmove(destination + at + by, source + at, oldchunksize - at);
  405.  
  406.       if(chunk != mem__lastchunk)
  407.       {
  408.         mem_header *next = (mem_header *)((int)newchunk + newchunksize);
  409.         next->prevrealsize = newchunksize;
  410.       }
  411.       else
  412.         mem__lastchunk = newchunk;      /* update mem__lastchunk */
  413.  
  414.       Mem__SplitOffFreeChunk(newchunk);
  415.     }
  416.   }
  417.  
  418.   mem__free -= needed;   /* successful allocation - update stats */
  419.  
  420.   return(TRUE);
  421. }
  422.